package com.LC.并归排序;


class MergeSort {
    public void mergeSort(int[] arr, int left, int right) {
        if(left<right){
            int mid = (left+right)/2;
            mergeSort(arr,left,mid);
            mergeSort(arr,mid+1,right);
            merge(arr,left,mid,right);
        }
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int[] temp =new int[right-left+1];  // 创建一个临时数组
        int i = left;
        int j = mid+1;  // 初始化两个指针
        int k = 0;  // 初始化临时数组的指针
        while(i<=mid&&j<=right){     // 当两个指针都没有超出范围时
            //从一个数组的两段区间中取出最小的放入临时数组 从最小的区间开始比较
            if(arr[i]<=arr[j]){         // 如果左边的数小于右边的数
                temp[k++] = arr[i++];   // 将小的数放入临时数组
            }
            else{                       // 如果右边的数小于左边的数
                temp[k++] = arr[j++];   // 将小的数放入临时数组
            }
        }
        while(i<=mid){ // 当左边指针没有超出范围时
            temp[k++] = arr[i++];
        }
        while(j<=right){ // 当右边指针没有超出范围时
            temp[k++] = arr[j++];
        }
        for(int m = 0; m<temp.length; m++){
            arr[left+m] = temp[m];
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 5, 3, 2, 4};
        MergeSort mergeSort = new MergeSort();
        mergeSort.mergeSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}